| 翻訳と辞書 |
| implication graph ： ウィキペディア英語版 |
implication graph
In mathematical logic, an implication graph is a skew-symmetric directed graph ''G''(''V'', ''E'') composed of vertex set ''V'' and directed edge set ''E''. Each vertex in ''V'' represents the truth status of a Boolean literal, and each directed edge from vertex ''u'' to vertex ''v'' represents the material implication "If the literal ''u'' is true then the literal ''v'' is also true". Implication graphs were originally used for analyzing complex Boolean expressions.
==Applications==
A 2-satisfiability instance in conjunctive normal form can be transformed into an implication graph by replacing each of its disjunctions by a pair of implications. An instance is satisfiable if and only if no literal and its negation belong to the same strongly connected component of its implication graph; this characterization can be used to solve 2-satisfiability instances in linear time.
In CDCL SAT-solvers, unit propagation can be naturally associated with an implication graph that captures all possible ways of deriving all implied literals from decision literals, which is then used for clause learning.
抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』
■ウィキペディアで「implication graph」の詳細全文を読む
スポンサード リンク
| 翻訳と辞書 : 翻訳のためのインターネットリソース |
Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.
|
|